package com.zjsru.oneDay;

/**
 * 城市天际线
 * 从数组的四个方向观察数字，获取最大值
 * 判断当前数字最多可以增加多少
 **/
public class citySky {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int ans = 0;
        int rowMax[] = new int[grid.length];
        int colMax[] = new int[grid.length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                rowMax[i] = Math.max(rowMax[i], grid[i][j]);
                colMax[j] = Math.max(colMax[j], grid[i][j]);
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                ans += Math.min(rowMax[i], colMax[j]) - grid[i][j];
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        citySky citySky = new citySky();
        System.out.println(citySky.maxIncreaseKeepingSkyline(new int[][]{{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0}}));
    }
}
